package com.carl.leetcode.backtracking;

/**
 * Created by carlXie on 2016/1/8.
 * email: kkrimen@gmail.com
 */
public class RegularExpressionMatching {
    public static void main(String[] args) {
        System.out.println(isMatch("aa", "a", 0, 0));
        System.out.println(isMatch("aa", "aa", 0, 0));
        System.out.println(isMatch("aaa", "aa", 0, 0));
        System.out.println(isMatch("aa", "a*", 0, 0));
        System.out.println(isMatch("aa", ".*", 0, 0));
        System.out.println(isMatch("ab", ".*", 0, 0));
        System.out.println(isMatch("aab", "c*a*b", 0, 0));

        System.out.println(isMatch("", "", 0, 0));
        System.out.println(isMatch("abcdeff", ".*", 0, 0));
        System.out.println(isMatch("a", "ab*", 0, 0));
        System.out.println(isMatch("bb", ".bab", 0, 0));
    }

    /**
     * 思路：看字符串s和p从开始到i和j的位置是否匹配，用递归的方法匹配到最后，最后回溯回来得到结果。
     * 假设现在从开始走到了s的i位置和p的j位置，下面分两种情况讨论：
     * 1. p[j+1]不是'*'：
     * 这种情况判断比较简单，只要判断s[i]和p[j]是否相等或者p[j]是否等于'*'，
     * 结果为真的话进入下一层i+1，j+1；否则直接返回false
     * 2. p[j+1]为'*'：
     * 这里也分三种情况讨论：
     * 1. 匹配到一个或多个，如aab与a*b:
     * 2. 匹配到0个，如abc与d*abc:
     * 3. *号前后相同，如aaa与a*a:
     *
     * @param s
     * @param p
     * @param i
     * @param j
     * @return
     */
    public static boolean isMatch(String s, String p, int i, int j) {
        // 终止条件：匹配到p字符串结束
        if (j == p.length())
            return i == s.length();
        // p[j+1] != '*'
        if (j == p.length() - 1 || p.charAt(j + 1) != '*') {
            if (i == s.length() || s.charAt(i) != p.charAt(j) && p.charAt(j) != '.')
                return false;
            else return isMatch(s, p, i + 1, j + 1);
        } else {
            // p[j+1] == '*'
            while (i < s.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.')) {
                // 检测*号前后相同的情况
                if (isMatch(s, p, i, j + 2))
                    return true;

                i++;
            }
            return isMatch(s, p, i, j + 2);
        }
    }
}
